package com.lz.sort;

import java.util.Arrays;

/**
 * 选择排序
 * 首先在未排序序列中找到最小（大）元素，存放到排序索引位置，
 * 然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排
 * 序序列的末尾。以此类推，直到所有元素均排序完毕。
 *
 * 时间复杂度与冒泡排序相同，但交换次数O(n)，冒泡排序交换O(n^2/2)
 *
 * @author: li
 * @date: 2019/1/18
 */
public class SelectionSort {
    public static void main(String[] args) {
        int[] x = {1, 2, 3, 4};
        int[] y = {4, 3, 2, 1};
        // sort(x);
        // sort(y);
        method01(y);
        System.out.println(Arrays.toString(x) + " : " + Arrays.toString(y));
    }

    private static void sort(int[] array) {
        int count = 0;
        for (int i = 0; i < array.length; i++) {
            int min = i;
            for (int j = i + 1; j < array.length; j++) {
                count++;
                if (array[min] > array[j]) {
                    min = j;
                }
            }
            if (min != i) {
                int temp = array[i];
                array[i] = array[min];
                array[min] = temp;
            }
        }
        System.out.println(count);
    }

    /**
     * 练习，核心思想
     * @param a
     */
    public static void method01(int a[]) {
        int len = a.length;
        for (int i = 0; i < len; i++) {
            // 核心
            int min = i;
            for (int j = i + 1; j < len; j++) {
                if (a[min] > a[j]) {
                    min = j;
                }
            }
            if (min != i) {
                int temp = a[i];
                a[i] = a[min];
                a[min] = temp;
            }
        }
    }
}
